/**
 * Created with IntelliJ IDEA.
 * Description:
 * 给你两个单链表的头节点headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 * 图示两个链表在节点 c1 开始相交：
 * User: xwl
 */

 class ListNode7 {
    int val;
    ListNode7 next;
    ListNode7(int x) {
        val = x;
        next = null;
    }
 }

public class Test9 {
    public ListNode7 getIntersectionNode(ListNode7 headA, ListNode7 headB) {
        // 定义俩个链表的长度
        int lenA = 0;
        int lenB = 0;
        // 定义俩个节点，分别指向俩个单链表的头节点
        ListNode7 pl = headA;
        ListNode7 ps = headB;
        // 遍历求长度
        while (pl != null) {
            lenA++;
            pl = pl.next;
        }
        while (ps != null) {
            lenB++;
            ps = ps.next;
        }
        // pl和ps指回来
        pl = headA;
        ps = headB;
        // 定义len为俩链表的差值
        int len = lenA - lenB;
        // 判断,使pl指向长链表
        if (len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        // 让长链表先走len步
        while (len != 0) {
            pl = pl.next;
            len--;
        }
        // 寻找相交节点,不相交时pl指向空
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        // 返回
        return pl;
    }
}
